# 417 中等: 太平洋大西洋水流问题
import numpy


def pacificAtlantic(heights):

    m = len(heights)
    n = len(heights[0])

    def dfs(x, y, arrs, vis, heights):

        vis[x][y] = 1

        move = [[-1, 0], [0, -1], [1, 0], [0, 1]]

        for j in range(4):
            tempx = x + move[j][0]
            tempy = y + move[j][1]
            if 0 <= tempx < len(arrs) and 0 <= tempy < len(arrs[0]):
                if vis[tempx][tempy] == 0 and heights[x][y] <= heights[tempx][tempy] and arrs[tempx][tempy] == 0:
                    arrs[tempx][tempy] = 1
                    dfs(tempx, tempy, arrs, vis, heights)

    # 初始化数组
    pacific, atlantic = [[0] * n for _ in range(m)], [[0] * n for _ in range(m)]
    for i in range(0, m):
        pacific[i][0] = 1
        atlantic[i][n - 1] = 1
    for i in range(0, n):
        pacific[0][i] = 1
        atlantic[m - 1][i] = 1
    vis = [[0] * n for _ in range(m)]

    # pacific
    for i in range(0, m):
        if vis[i][0] == 0:
            dfs(i, 0, pacific, vis, heights)
    for j in range(0, n):
        if vis[0][j] == 0:
            dfs(0, j, pacific, vis, heights)

    # atlantic
    vis = [[0] * n for _ in range(m)]
    for i in range(0, m):
        if vis[i][n - 1] == 0:
            dfs(i, n - 1, atlantic, vis, heights)
    for j in range(0, n):
        if vis[m - 1][j] == 0:
            dfs(m - 1, j, atlantic, vis, heights)

    # both
    both = numpy.array(pacific) + numpy.array(atlantic)

    # print(pacific)
    # print(atlantic)
    # print(both)

    ret = numpy.argwhere(both == 2)
    print(type(ret.tolist()))

    return ret.tolist()


print(pacificAtlantic([[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]))
print(pacificAtlantic([[2,1],[1,2]]))


# class Solution:
#     def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
#         m, n = len(heights), len(heights[0])
#
#         def search(starts: List[Tuple[int, int]]) -> Set[Tuple[int, int]]:
#             visited = set()
#             def dfs(x: int, y: int):
#                 if (x, y) in visited:
#                     return
#                 visited.add((x, y))
#                 for nx, ny in ((x, y + 1), (x, y - 1), (x - 1, y), (x + 1, y)):
#                     if 0 <= nx < m and 0 <= ny < n and heights[nx][ny] >= heights[x][y]:
#                         dfs(nx, ny)
#             for x, y in starts:
#                 dfs(x, y)
#             return visited
#
#         pacific = [(0, i) for i in range(n)] + [(i, 0) for i in range(1, m)]
#         atlantic = [(m - 1, i) for i in range(n)] + [(i, n - 1) for i in range(m - 1)]
#         return list(map(list, search(pacific) & search(atlantic)))
